<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>String Interleaving</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="string-interleaving">String Interleaving</h1>
<p>leetcode 97. Interleaving String</p>
<ul>
<li><a href="https://www.youtube.com/watch?v=ih2OZ9-M3OM&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=33">https://www.youtube.com/watch?v=ih2OZ9-M3OM&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=33</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/TwoStringInterleavingToFormThird.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/TwoStringInterleavingToFormThird.java</a></li>
<li><a href="https://leetcode.com/problems/interleaving-string/">https://leetcode.com/problems/interleaving-string/</a></li>
</ul>
<h2 id="11-top-to-down-dfs--memo">1.1 top to down, dfs + memo</h2>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> functools <span class="hljs-keyword">import</span> lru_cache

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isInterleave</span><span class="hljs-params">(self, s1: str, s2: str, s3: str)</span> -&gt; bool:</span>
        
<span class="hljs-meta">        @lru_cache</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_dfs</span><span class="hljs-params">(i, j, k)</span>:</span>
            <span class="hljs-keyword">if</span> i == <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> j == <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> k == <span class="hljs-number">0</span>:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
            
            <span class="hljs-keyword">if</span> i&gt;<span class="hljs-number">0</span> <span class="hljs-keyword">and</span> s1[i<span class="hljs-number">-1</span>] == s3[k<span class="hljs-number">-1</span>] <span class="hljs-keyword">and</span> _dfs(i<span class="hljs-number">-1</span>, j, k<span class="hljs-number">-1</span>):
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
            
            <span class="hljs-keyword">if</span> j&gt;<span class="hljs-number">0</span> <span class="hljs-keyword">and</span> s2[j<span class="hljs-number">-1</span>] == s3[k<span class="hljs-number">-1</span>] <span class="hljs-keyword">and</span> _dfs(i, j<span class="hljs-number">-1</span>, k<span class="hljs-number">-1</span>):
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
            
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        
        m = len(s1)
        n = len(s2)
        k = len(s3)
        <span class="hljs-keyword">if</span> n+m != k:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        
        <span class="hljs-keyword">return</span> _dfs(m, n, k)
</div></code></pre>
<h1 id="12-bottom-to-top-dp">1.2 bottom to top, dp</h1>
<p>注意，这个循环判断是 range(0, 1+m), 而不是常见的 range(1, 1+m)</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> functools <span class="hljs-keyword">import</span> lru_cache

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isInterleave</span><span class="hljs-params">(self, s1: str, s2: str, s3: str)</span> -&gt; bool:</span>

        m = len(s1)
        n = len(s2)
        k = len(s3)
        <span class="hljs-keyword">if</span> n+m != k:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>

        dp = [[<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(m+<span class="hljs-number">1</span>)]
        dp[<span class="hljs-number">0</span>][<span class="hljs-number">0</span>] = <span class="hljs-number">1</span>
        
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">0</span>, <span class="hljs-number">1</span>+m):  <span class="hljs-comment"># s1</span>
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">0</span>, <span class="hljs-number">1</span>+n): <span class="hljs-comment"># s2</span>
                <span class="hljs-keyword">if</span> j &gt; <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> s2[j<span class="hljs-number">-1</span>] == s3[i+j<span class="hljs-number">-1</span>] <span class="hljs-keyword">and</span> dp[i][j<span class="hljs-number">-1</span>]:
                    dp[i][j] = <span class="hljs-number">1</span>
                <span class="hljs-keyword">if</span> i &gt; <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> s1[i<span class="hljs-number">-1</span>] == s3[i+j<span class="hljs-number">-1</span>] <span class="hljs-keyword">and</span> dp[i<span class="hljs-number">-1</span>][j]:
                    dp[i][j] = <span class="hljs-number">1</span>
    
        <span class="hljs-keyword">return</span> dp[m][n]
</div></code></pre>
<p>或者提前对第0行， 第0列赋值</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isInterleave</span><span class="hljs-params">(self, s1: str, s2: str, s3: str)</span> -&gt; bool:</span>
        x, y, z = len(s1), len(s2), len(s3)
        <span class="hljs-keyword">if</span> x+y != z:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        matrix = [[<span class="hljs-literal">True</span>] * (y+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(x+<span class="hljs-number">1</span>)]
        <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>,y+<span class="hljs-number">1</span>):
            matrix[<span class="hljs-number">0</span>][j] = matrix[<span class="hljs-number">0</span>][j<span class="hljs-number">-1</span>] <span class="hljs-keyword">and</span> s2[j<span class="hljs-number">-1</span>] == s3[j<span class="hljs-number">-1</span>]
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, x+<span class="hljs-number">1</span>):
            matrix[i][<span class="hljs-number">0</span>] = matrix[i<span class="hljs-number">-1</span>][<span class="hljs-number">0</span>] <span class="hljs-keyword">and</span> s1[i<span class="hljs-number">-1</span>] == s3[i<span class="hljs-number">-1</span>]
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, x+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, y+<span class="hljs-number">1</span>):
                matrix[i][j] = (matrix[i][j<span class="hljs-number">-1</span>] <span class="hljs-keyword">and</span> s2[j<span class="hljs-number">-1</span>] == s3[i+j<span class="hljs-number">-1</span>]) <span class="hljs-keyword">or</span> \
                           (matrix[i<span class="hljs-number">-1</span>][j] <span class="hljs-keyword">and</span> s1[i<span class="hljs-number">-1</span>] == s3[i+j<span class="hljs-number">-1</span>])
        <span class="hljs-keyword">return</span> matrix[x][y]
</div></code></pre>

    </body>
    </html>